package com.lili.other;

import java.util.HashMap;

/**
 * @Auther: 李 力
 * @Date: 2024/8/22
 * @Description: 460. LFU缓存
 * @version: 1.0
 */
public class LFUCache {

    private HashMap<Integer, Node> kvMap = new HashMap<>();

    private HashMap<Integer, DTLinkedList> freqMap = new HashMap<>();

    private int capacity;

    private int minFreq = 1;//最小频度

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!kvMap.containsKey(key)) {
            return -1;
        }
        Node node = kvMap.get(key);

        freqMap.get(node.freq).remove(node);

        if (freqMap.get(node.freq).isEmpty() && node.freq == minFreq) {
            minFreq++;
        }

        node.freq++;
//        DTLinkedList dtLinkedList = freqMap.get(node.freq);
//        if (dtLinkedList == null) {
//            dtLinkedList = new DTLinkedList();
//            freqMap.put(node.freq, dtLinkedList);
//        }
//        dtLinkedList.addFirst(node);
        freqMap.computeIfAbsent(node.freq, k -> new DTLinkedList()).addFirst(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (kvMap.containsKey(key)) {
            Node node = kvMap.get(key);
            freqMap.get(node.freq).remove(node);
            if (freqMap.get(node.freq).isEmpty() && node.freq == minFreq) {
                minFreq++;
            }
            node.freq++;
            freqMap.computeIfAbsent(node.freq, k -> new DTLinkedList()).addFirst(node);
            node.value = value;
        } else {
            if (kvMap.size() == capacity) {
                Node node = freqMap.get(minFreq).removeLast();
                kvMap.remove(node.key);
            }
            Node node = new Node(key, value);
            kvMap.put(key, node);
            freqMap.computeIfAbsent(1, k -> new DTLinkedList()).addFirst(node);
            minFreq = 1;
        }
    }

    static class Node {
        Node prev;
        Node next;
        int key;
        int value;
        int freq = 1;//使用频度

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node() {
        }
    }

    static class DTLinkedList {
        Node head;
        Node tail;
        int size;//链表长度

        public DTLinkedList() {
            head = tail = new Node();
            head.next = tail;
            tail.prev = head;
        }

        //头部添加
        public void addFirst(Node node) {
            Node first = head.next;
            node.prev = head;
            node.next = first;
            head.next = node;
            first.prev = node;
            size++;
        }

        public Node removeLast() {
            Node last = tail.prev;
            remove(last);
            return last;
        }

        public void remove(Node node) {
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            size--;
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }
}
